Năm 1865, Claude Lee Moses, lãnh sự Hoa Kỳ tại Brunei, ký được hợp đồng thuê đất Bắc Borneo trong thời hạn 10 năm với Brunei. Tuy vậy, chính phủ thời hậu chiến của Mĩ không muốn đụng chạm nhiều tới các phần thuộc địa Á châu nên Moses đã nhượng lại quyền thuê đất này cho American Trading Company. Do vướng phải những khó khăn tài chính nên sau đó công ty này lại nhượng quyền thuê đất trên cho Nam tước Gustavus von Overbeck. Von Overbeck đã kiếm được một thỏa thuận gia hạn hợp đồng thuê đất thêm 10 năm nữa từ Temenggong của Brunei, và cũng kiếm được một thỏa thuận tương tự từ phía vua Sulu vào ngày 22 tháng 1 năm 1878.

Nhằm trang trải cho kế hoạch trên, von Overbeck tìm kiếm sự hậu thuẫn của anh em nhà Dent - làAlfred và Edward. Dẫu vậy, von Overbeck không thuyết phục nổi chính phủ về những mối lời nhìn thấy được từ dự án này. Kết quả là von Overbeck bỏ cuộc để lại cho Afred Dent quyền cai quản phần đất thuê được. Đó là vào thời điểm năm 1880.

Được sự hậu thuẫn của Sir Rutherford Alcock và Sir Henry Keppel, Đô đốc của Hải quân Hoàng gia Anh, vào tháng 7 năm 1881, anh em nhà Dent lập ra British North Borneo Provisional Association Ltd. Cũng như giấy nhượng đất chính thức của Hoàng gia vào ngày 1 tháng 9 cùng năm, để rồi vào tháng 5 năm 1882, British North Borneo Chartered Company ra đời và chính thức thay thế cho công ty lâm thời đã kể ở trên. Sir Rutherford Alcock trở thành chủ tịch sáng lập, còn Alfred là giám đốc điều hành.

Dù gặp một vài phản đối về mặt ngoại giao từ Hà Lan, Tây Ban Nha và Sarawak (khi này Sarawak chịu sự cai trị của dòng họ Brooke da trắng, những người đã lên ngôi vua từ cách đó khoảng 50 năm), British North Borneo Company vẫn tiến hành tổ chức cái quản và sắp xếp lại mảnh đất này. Sau đó, công ty này nhận được sự thừa nhận về chủ quyền đất đai từ phía nhà vua Brunei và không ngừng mở rộng lãnh thổ.

Năm 1888, Bắc Borneo trở thành đất bảo hộ của Đế quốc Anh. Tuy vậy thì British North Borneo Company vẫn tiếp tục được cai quản trực tiếp, Hoàng gia Anh chỉ can thiệp và chủ trì về sự vụ ngoại giao mà thôi.

Như vậy, cho tới nửa sau thế kỉ 19, Sulu đã từng bước và cuối cùng là hoàn toàn mất phần đất bắc Borneo. Câu chuyện này trùng khít với sự suy sụp không thể ngăn chặn nổi của Vương quốc Hồi giáo này. Cuối cùng, vào năm 1899, sau khi vị vua có thực quyền cuối cùng của Sulu qua đời, vương quốc này trở thành lãnh thổ của Philippines.

Các Sultan của Sulu:

1. Sharif ul-Hashim: 1450-1480
2. Kamalud-Din: 1480-1505
3. Alaud-Din: 1505
4. Amirul-Umara: 1505-1527
5. Muizzul-Mutawadi: 1527-1548
6. Nasirud-Din I: 1548-1568
7. Muhammad ul-Halim: 1568-1596
8. Batara Shah Tengah: 1596-1608
9. Muwallil Wasit I: 1610-1645
10. Nasir ud-Din II: 1645-1648
11. Salahud-Din Bakhtiar: 1649-1680
12. Ali Shah
13. Nur Sultan ul-Azam
14. Al Haqunu Ibn Wali ul-Ahad
15. Shahabud-Din: 1685-1710
16. Mustafa Shafi ud-Din: 1710-1718
17. Badarud-Din I: 1718-1732
18. Nasarud-Din: 1732-1735
19. Alimud-Din I: 1735-1748; 1764-1773
20. Bantilan Muizzud-Din: 1748-1763
21. Mohammad Israel: 1773-1778
22. Alimud-Din II: 1763-1764; 1778-1789
23. Sharapud-Din: 1789-1808
24. Alimud-Din III: 1808
25. Aliyud-Din I: 1808-1821
26. Shakirul-Lah: 1821-1823
27. Jamalul-Kiram I: 1823-1844
28. Mohammed Pulalun Kiram: 1844-1862
29. Jamalul A'Lam: 1862-1881
30. Badarud-Din II: 1881-1884
31. Harun Ar-Rashid: 1886-1894
32. Jamalul-Kiram II: 1894-1936
33. Muwallil Wasit II: 1936
34. Amirul Umara I: 1937-1950
35. Jainal Abirin: 1937-1950
36. Sultan Mohammed Esmail El Kiram I: 1950-1974
37. Sultan Moh. Mahakuttah A. Kiram: 1974-1980
38. Moh. Punjungan Kiram: 1980-1983
39. Abirin Aguimuddin: 1983
40. Jamal ul-Kiram III: 1983-1990
41. Jamal ul-Kiram III: 1983-1990

Raja Muda Muedzul Lail Tân Kiram: 1986-nay

1. Mohammad Akijal Atti: 1990-1999
2. Ismael Kiram II: 1999 - nay